package com.company.hash;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by v on 16-12-7.
 * 分离链接散列表
 */
public class SeparateChainingHashTable<E> {
    private static final int DEFAULT_TABLE_SIZE=101;

    private int currentSize;
    private List<E>[] theLists;


    public SeparateChainingHashTable(){
        this(DEFAULT_TABLE_SIZE);
    }

    public SeparateChainingHashTable(int size){
        theLists=new List[Prime.nextPrime(size)];
        clear();
    }

    //散列表插入
    public boolean insert(E e){
        List<E> whichList=theLists[myhash(e)];
        //若已存在，则不插入
        if(whichList.contains(e)){
            return false;
        }

        whichList.add(e);
        if(++currentSize>theLists.length){
            rehash();
        }
        return true;
    }

    //散列表删除
    public boolean remove(E e){
        List<E> whichList=theLists[myhash(e)];
        if(whichList.remove(e)){
            currentSize--;
            return true;
        }
        return false;
    }

    //散列表查找
    public boolean contains(E e){
        List<E> whichList=theLists[myhash(e)];
        return whichList.contains(e);
    }

    //清空散列表
    public void clear(){
        for(int i=0;i<theLists.length;i++){
            theLists[i]=new LinkedList<E>();
            currentSize=0;
        }
    }

    //再散列
    private void rehash(){
        List<E>[] temp=theLists.clone();
        theLists=new List[Prime.nextPrime(theLists.length*2)];
        clear();
        for(int i=0;i<temp.length;i++){
            for(E e:temp[i]){
                insert(e);
            }
        }
    }

    //散列函数
    private int myhash(E e){
        int hashVal=e.hashCode();

        hashVal%=theLists.length;
        if(hashVal<0){
            hashVal+=theLists.length;
        }
        return hashVal;
    }
}
